/**
 * 
 */
package edu.rice.test;

import java.awt.Color;
import java.awt.Graphics2D;
import java.awt.geom.Ellipse2D;
import java.awt.geom.Rectangle2D;
import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Random;

import javax.imageio.ImageIO;

/**
 * @author frogy
 * 
 */
public class CellPush {

	public static void main(String[] args) {
		long timeStart = System.currentTimeMillis();
		new CellPush(50, 100, 1);
		long timeEnd = System.currentTimeMillis();
		System.out.println("total time: " + (timeEnd - timeStart));
	}

	private int N;

	private double L;

	private double d;

	private Cell[] x;

	private Cell[] xn;

	private Cell[] xini;

	private ArrayList<Cell> leftlist;

	private ArrayList<Cell> rightlist;

	public CellPush(int N, double L, double d) {
		this.N = N;
		this.L = L;
		this.d = d;
		x = new Cell[N];
		xini = new Cell[N];
		xn = new Cell[2 * N];
		leftlist = new ArrayList<Cell>();
		rightlist = new ArrayList<Cell>();
		Random r = new Random();
		r.setSeed(123456789);
		for (int i = 0; i < x.length; i++) {
			double tempx = r.nextDouble() * L;
			x[i] = new Cell(tempx, i);
			xini[i] = new Cell(tempx, i);
		}
		findNeighbor();
		for (int i = 0; i < x.length; i++) {
			findLeftOverlap(i);
			findRightOverlap(i);
			if (leftlist.size() == 0 && rightlist.size() == 0) {
				continue;
			}
			double freespace = computeFreeSpace(i);
			double expandspace = computeExpanSpace();
			while (freespace < expandspace
					&& leftlist.size() + 1 + rightlist.size() < N) {
				// add two ends
				int leftleft, rightright;
				if (leftlist.size() > 0) {
					leftleft = 2 * leftlist.get(leftlist.size() - 1).getId();
				} else {
					leftleft = 2 * i;
				}
				if (rightlist.size() > 0) {
					rightright = 2 * rightlist.get(rightlist.size() - 1)
							.getId() + 1;
				} else {
					rightright = 2 * i + 1;
				}
				if (xn[leftleft].getId() >= 0) {
					leftlist.add(xn[leftleft]);
				}
				if (xn[rightright].getId() < N) {
					rightlist.add(xn[rightright]);
				}
				freespace = computeFreeSpace(i);
				expandspace = computeExpanSpace();
			}
			expand(i, expandspace, freespace);
			leftlist.clear();
			rightlist.clear();
			findNeighbor();
		}
		
		double chAve = 0;
		double chMax = 0;
		double chMin = 100;
		int numMoved = 0;
		for (int i = 0; i < 50; i++) {
			double ch = Math.abs(x[i].getX() - xini[i].getX());
			if (ch > 0) {
				numMoved++;
				if (ch > chMax) {
					chMax = ch;
				}
				if (ch < chMin) {
					chMin = ch;
				}
			}
			chAve += ch;
		}
		chAve /= (double) numMoved;
		System.out.println("On average, each moved cell moved " + chAve + ".");
		System.out.println("Max displacement is " + chMax + ".");
		System.out.println("Min displacement is " + chMin + ".");
		createImage();
	}

	private void createImage() {
		BufferedImage bufferedImage = new BufferedImage(1010, 600,
				BufferedImage.TYPE_3BYTE_BGR);
		Graphics2D g2 = bufferedImage.createGraphics();
		g2.setColor(Color.WHITE);
		g2.fill(new Rectangle2D.Double(0, 0, 1010, 600));
		g2.setColor(Color.red);
		for (int i = 0; i < x.length; i++) {
			g2.draw(new Ellipse2D.Double(xini[i].getX() * 10, 100, 10, 10));
			g2.draw(new Ellipse2D.Double(x[i].getX() * 10, 500, 10, 10));
		}
		try {
			File imOut = new File("balls.png");
			ImageIO.write(bufferedImage, "png", imOut);
		} catch (IOException e) {
		}
	}

	private void findNeighbor() {
		for (int i = 0; i < x.length; i++) {
			Cell[] temp = findNeighbor(i);
			xn[2 * i] = temp[0];
			xn[2 * i + 1] = temp[1];
		}
	}

	private Cell[] findNeighbor(int cellId) {
		Cell[] nei = new Cell[2];
		nei[0] = new Cell(0, -1);
		nei[1] = new Cell(L, N);
		for (int i = 0; i < x.length; i++) {
			if (x[i].getX() > nei[0].getX() && x[i].getX() < x[cellId].getX()) {
				nei[0] = x[i];
			}
			if (x[i].getX() > x[cellId].getX() && x[i].getX() < nei[1].getX()) {
				nei[1] = x[i];
			}
		}
		return nei;

	}

	private void findLeftOverlap(int id) {
		int start = id;
		int startn = 2 * id; // left
		while (xn[startn].getId() >= 0 && xn[startn].getId() < N
				&& dis(x[start], xn[startn]) < d) {
			// do not add boundary
			leftlist.add(xn[startn]);
			start = xn[startn].getId();
			startn = 2 * start;
		}
	}

	private void findRightOverlap(int id) {
		int start = id;
		int startn = 2 * id + 1;
		while (xn[startn].getId() >= 0 && xn[startn].getId() < N
				&& dis(x[start], xn[startn]) < d) {
			// do not add boundary
			rightlist.add(xn[startn]);
			start = xn[startn].getId();
			startn = 2 * start + 1;
		}
	}

	/**
	 * Expan the overlapping cell cluster initiated by cell[id]
	 * 
	 * @param id
	 */
	private void expand(int id, double expandSpace, double freeSpace) {
		int leftbound, rightbound;
		if (leftlist.size() == 0) {
			leftbound = id * 2;
		} else {
			leftbound = leftlist.get(leftlist.size() - 1).getId() * 2;
			// leftmost cell's left neighbor is the left bound
		}
		if (rightlist.size() == 0) {
			rightbound = id * 2 + 1;
		} else {
			rightbound = rightlist.get(rightlist.size() - 1).getId() * 2 + 1;
			// rightmost cell's right neighbor is the right bound
		}
		double massCenter = 0;
		for (int i = 0; i < leftlist.size(); i++) {
			massCenter += leftlist.get(i).getX();
		}
		for (int i = 0; i < rightlist.size(); i++) {
			massCenter += rightlist.get(i).getX();
		}
		int nc = leftlist.size() + rightlist.size() + 1;
		massCenter += x[id].getX();
		massCenter /= (double) nc;
		ArrayList<Cell> alllist = new ArrayList<Cell>();
		// from left to right
		for (int i = leftlist.size() - 1; i >= 0; i--) {
			alllist.add(leftlist.get(i));
		}
		alllist.add(x[id]);
		for (int i = 0; i < rightlist.size(); i++) {
			alllist.add(rightlist.get(i));
		}

		double increase = freeSpace / (double) nc;
		increase = d;

		// Then there are two conditions
		// 1. if the shorter distance from mass center to two bounds are larger
		// than half of the expand Space
		// Then the expand space should be centered at the mass center
		// 2. if the shorter distance from mass center to two bounds are smaller
		// than half of the expand space
		// Then the expand space should be start from the near bound
		if (min(Math.abs(massCenter - xn[leftbound].getX()), Math
				.abs(massCenter - xn[rightbound].getX())) > expandSpace / 2) {

			if (nc % 2 == 0) {
				double start = massCenter - increase * (double) nc / 2;
				for (int i = 0; i < nc; i++) {
					alllist.get(i).setX(start);
					start += increase;
				}
			} else {
				double start = massCenter - increase * (double) (nc - 1) / 2
						- d / 2;
				for (int i = 0; i < nc; i++) {
					alllist.get(i).setX(start);
					start += increase;
				}
			}
		} else {
			// if left bound is nearer, then start from left bound
			if (Math.abs(massCenter - xn[leftbound].getX()) < Math
					.abs(massCenter - xn[rightbound].getX())) {
				double start = xn[leftbound].getX() + increase;
				for (int i = 0; i < nc; i++) {
					alllist.get(i).setX(start);
					start += increase;
				}
			} else { // if right bound is nearer, start from right bound
				double start = xn[rightbound].getX() - increase;
				for (int i = nc - 1; i >= 0; i--) {
					alllist.get(i).setX(start);
					start -= increase;
				}
			}
		}
	}

	/**
	 * Calculate space needed to expand
	 * 
	 * @param list
	 * @return
	 */
	private double computeExpanSpace() {
		double dis = 0;
		int numCell = 0;
		numCell += leftlist.size();
		numCell += rightlist.size();
		numCell += 1;
		// add itself
		dis = (double) numCell * d;
		return dis;
	}

	/**
	 * Calculate free space bound by no overlapping neighbors The free space is
	 * for distributing overlapping cells
	 * 
	 * @param leftlist
	 * @param rightlist
	 * @return
	 */
	private double computeFreeSpace(int id) {
		double dis = 0;
		int leftbound, rightbound;
		if (leftlist.size() == 0) {
			leftbound = id * 2;
		} else {
			leftbound = leftlist.get(leftlist.size() - 1).getId() * 2;
			// leftmost cell's left neighbor is the left bound
		}
		if (rightlist.size() == 0) {
			rightbound = id * 2 + 1;
		} else {
			rightbound = rightlist.get(rightlist.size() - 1).getId() * 2 + 1;
			// rightmost cell's right neighbor is the right bound
		}
		dis = Math.abs(xn[rightbound].getX() - xn[leftbound].getX()) - d;
		// Consider the length of the segments
		// free space is center distance minus d;
		return dis;
	}

	private static double min(double a, double b) {
		return a < b ? a : b;
	}

	private double dis(Cell a, Cell b) {
		return Math.abs(a.getX() - b.getX());
	}

}

class Cell {

	public Cell(double x, int id) {
		this.x = x;
		this.id = id;
	}

	private double x;

	private int id;

	/**
	 * @param x
	 *            the x to set
	 */
	public void setX(double x) {
		this.x = x;
	}

	/**
	 * @return the x
	 */
	public double getX() {
		return x;
	}

	/**
	 * @return the id
	 */
	public int getId() {
		return id;
	}

	/**
	 * @param id
	 *            the id to set
	 */
	public void setId(int id) {
		this.id = id;
	}

}
